
import java.util.Arrays;

public class e070 {
    public static void main(String[] args) {
        long sTime = System.currentTimeMillis();
        double smallest = 100000000;
        long smallNum = 0;
        System.out.println(Totient(8319823));
        for (long n = 2; n < 10000000; n++) {
            long i = Totient((double)n);
            if (arePermu(n, i)) {
                double j = (double)n / (double)Totient(n);
                if (j < smallest) {
                    smallest = j;
                    smallNum = n;
                }
            }
        }
        System.out.println(smallNum);
        long fTime = System.currentTimeMillis();
        System.out.println("Time: " + (fTime - sTime) + "ms");
    }

    public static long Totient(double n) {
        double c = n;
        for (double i = 2; i <= Math.sqrt(n); ++i) {
            int subcount = 0;
            while (n % i == 0) {
                subcount++;
                n /= i;
            }
            if (subcount > 0) {
                double m = (1 - 1 / i);
                c *= m;
            }
        }
        if (n > 1) {
            double m = (1 - 1 / n);
            c *= m;
        }
        return Math.round(c);
   }

    static int gcd(int a, int b) {
        boolean found = false;
        int mod = a % b;
        while(true) {
            if (mod == 0) {
                return b;
            }
            int oldB = b;
            b = mod;
            mod = oldB % b;
        }
    }

    static boolean arePermu(long x, long y) {
        StringBuilder a = new StringBuilder(String.valueOf(x));
        StringBuilder b = new StringBuilder(String.valueOf(y));
        if (a.length() != b.length()) {
            return false;
        }
        char aIndex[] = new char[a.length()];
        char bIndex[] = new char[b.length()];
        for(int i = 0; i < a.length(); i++) {
            aIndex[i] = a.charAt(i);
            bIndex[i] = b.charAt(i);
        }
        Arrays.sort(aIndex);
        Arrays.sort(bIndex);
        int numSame = 0;
        for(int i = 0; i < aIndex.length; i++) {
            if (aIndex[i] == bIndex[i]) {
                numSame++;
            }
        }
        return (numSame == a.length());
    }
}